package com.fr.sudoku;

import org.junit.Test;

public class Sudoku {
    private BaseInfo[][] base = new BaseInfo[9][9];

    @Test
    public void sudoku() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                base[i][j] = new BaseInfo(0);
            }
        }
        base[0][1] = new BaseInfo(6, true);
        base[0][3] = new BaseInfo(8, true);
        base[1][1] = new BaseInfo(2, true);
        base[1][3] = new BaseInfo(4, true);
        base[1][6] = new BaseInfo(9, true);
        base[2][1] = new BaseInfo(3, true);
        base[2][5] = new BaseInfo(6, true);
        base[2][6] = new BaseInfo(1, true);
        base[2][7] = new BaseInfo(4, true);
        base[2][8] = new BaseInfo(8, true);
        base[3][0] = new BaseInfo(5, true);
        base[3][2] = new BaseInfo(1, true);
        base[3][5] = new BaseInfo(8, true);
        base[3][8] = new BaseInfo(9, true);
        base[4][5] = new BaseInfo(4, true);
        base[4][7] = new BaseInfo(3, true);
        base[4][8] = new BaseInfo(2, true);
        base[5][0] = new BaseInfo(3, true);
        base[5][4] = new BaseInfo(9, true);
        base[5][5] = new BaseInfo(5, true);
        base[5][7] = new BaseInfo(1, true);
        base[6][6] = new BaseInfo(3, true);
        base[6][8] = new BaseInfo(4, true);
        base[8][0] = new BaseInfo(8, true);
        base[8][1] = new BaseInfo(9, true);
        base[8][6] = new BaseInfo(2, true);
        sudoku(0, 0);
    }

    public void sudoku(int i, int j) {
        if (i == 9 && j == 0) {
            show();
        } else {
            if (base[i][j].change) {
                if (j == 8) {
                    sudoku(i + 1, 0);
                } else {
                    sudoku(i, j + 1);
                }
            } else {
                for (int k = 1; k <= 9; k++) {
                    if (check(i, j, k)) {
                        base[i][j].num = k;
                        if (j == 8) {
                            sudoku(i + 1, 0);
                        } else {
                            sudoku(i, j + 1);
                        }
                        base[i][j].num = 0;
                    }
                }
            }
        }
    }

    private boolean check(int i, int j, int k) {
        for (int p = 0; p < 9; p++) {
            if (base[p][j].num == k) {
                return false;
            }
        }
        for (int p = 0; p < 9; p++) {
            if (base[i][p].num == k) {
                return false;
            }
        }
        int a = i / 3;
        int b = j / 3;
        for (int p = 0; p < 3; p++) {
            for (int q = 0; q < 3; q++) {
                if (base[3 * a + p][3 * b + q].num == k) {
                    return false;
                }
            }
        }
        return true;
    }

    private void show() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(base[i][j].num + "\t");
            }
            System.out.println();
        }
        System.exit(1);
    }

    class BaseInfo {
        int num = 0;
        boolean change = false;

        public BaseInfo(int num) {
            this.num = num;
        }

        public BaseInfo(int num, boolean change) {
            this.num = num;
            this.change = change;
        }

        @Override
        public String toString() {
            return "BaseInfo [num=" + num + ", change=" + change + "]";
        }

    }

}
